package com.sk.leetcode.arithmetic;

/**
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * 示例 1:
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * 示例 2:
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 * 说明:
 * 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
 */
public class Test215 {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 4, 7, 23, 4, 56, 78, 9, 100};
        int res = findKthLargest(nums, 1);
        System.out.println(res);
    }

    public static int findKthLargest(int[] nums, int k) {
        Nums last = new Nums();
        last.val = nums[0];
        Nums.length = 1;
        for (int i = 1; i < nums.length; i++) {
            last = ch(nums[i], last, k);
        }
        return last.val;
    }

    private static Nums ch(int num, Nums nums, int k) {
        Nums last = nums;
        if(Nums.length < k) {
            Nums.length++;
            return js(nums, num);
        } else {
            if(nums.val >= num) {
                return last;
            } else {
                Nums pre = nums.pre;
                if(pre == null) {
                    last = new Nums();
                    last.val = num;
                    return last;
                }
                nums = pre;
                last = nums;
                return js(nums, num);
            }
        }
    }

    private static Nums js(Nums nums, int num) {
        boolean b = true;
        Nums last = nums;
        while (true) {
            if(nums.val >= num) {
                Nums next = nums.next;
                nums.next = new Nums();
                nums.next.val = num;
                nums.next.pre = nums;
                if(next != null) {
                    nums.next.next = next;
                    next.pre = nums.next;
                }
                if(b) {
                    return nums.next;
                }
                return last;
            } else {
                if(nums.pre == null) {
                    nums.pre = new Nums();
                    nums.pre.val = num;
                    nums.pre.next = nums;
                    return last;
                } else {
                    nums = nums.pre;
                }
            }
            b = false;
        }
    }
}

class Nums {
    static int length = 0;
    public int val;
    public Nums next;
    public Nums pre;
}